﻿/*
Ugly Numbers 
Time Limit:1000MS  Memory Limit:32768K


Description:
Ugly numbers are numbers whose only prime factors are 2, 3 or 5.
The sequence 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ... shows the first 11 ugly numbers.
By convention, 1 is included. Write a program to find and print the n’th ugly number. 

Input:
Every integer number (≤1500)describing position of ugly number from 1.
If integer number is 0,the process should ended.
Maybe there are 10000 integer numbers on input data. 
Output:
Every integer given should output a line as shown below, The <n>th ugly number is <number>.
with <n> replaced by the integer number and <number> replaced by the number computed. 
Sample Input:
5 16
Sample Output:
The 5th ugly number is 5.
The 16th ugly number is 25.
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
using namespace std;

unsigned min3(unsigned a, unsigned b, unsigned c)
{
	if(c>a)
		c=a;
	if(c>b)
		c=b;
	return c;
}
int main()
{
	vector<unsigned> nths;
	for (unsigned nth; cin >> nth; nths.push_back(nth))
		;
	unsigned max_nth=*max_element(nths.begin(), nths.end());

	vector<unsigned> uglies;
	uglies.reserve(max_nth+1);
	//
	{
		for (unsigned i=0; i<=5; ++i)
			uglies.push_back(i);
	}
	//~

	{
		unsigned i2=3, i3=2, i5=2;
		for (unsigned i=5+1; i<=max_nth; ++i)
		{
			unsigned back=min3(uglies[i2]*2, uglies[i3]*3, uglies[i5]*5);
			uglies.push_back(back);
			while (uglies[i2]*2<=back)
				++i2;
			while (uglies[i3]*3<=back)
				++i3;
			while (uglies[i5]*5<=back)
				++i5;
		}

	}
	
	for (unsigned i=0, size=nths.size(); i<size; ++i)
	{
		cout<<"The "<<nths[i]<<"th ugly number is "<<uglies[nths[i]]<<"."<<endl;
	}


	return EXIT_SUCCESS;
}
